/**
 * 
 */
package graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * @author michael
 *
 */
public class CloneGraph {

	/**
	Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
	
	
	OJ's undirected graph serialization:
	Nodes are labeled uniquely.
	
	We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
	As an example, consider the serialized graph {0,1,2#1,2#2,2}.
	
	The graph has a total of three nodes, and therefore contains three parts as separated by #.
	
	First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
	Second node is labeled as 1. Connect node 1 to node 2.
	Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
	Visually, the graph looks like the following:
	
	       1
	      / \
	     /   \
	    0 --- 2
	         / \
	         \_/
	 */
	/**
	 * Definition for undirected graph.
	 */
	class UndirectedGraphNode {
	    int label;
	    List<UndirectedGraphNode> neighbors;
	    UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
	};
	
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return node;
    	
    	Queue<UndirectedGraphNode> queue = new LinkedList<>();
    	queue.add(node);
    	
    	Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
    	UndirectedGraphNode copyNode = new UndirectedGraphNode(node.label);
    	map.put(node, copyNode);
    	while (!queue.isEmpty()) {
    		UndirectedGraphNode currNode = queue.poll();
    		List<UndirectedGraphNode> neighbors = currNode.neighbors;
    		for (UndirectedGraphNode neighbor : neighbors) {
    			if (map.containsKey(neighbor)) {
    				map.get(currNode).neighbors.add(map.get(neighbor));
    			}
    			else {
    				UndirectedGraphNode copyNeighbor = new UndirectedGraphNode(neighbor.label);
    				map.put(neighbor, copyNeighbor);
    				map.get(currNode).neighbors.add(copyNeighbor);
    				queue.add(neighbor);
    			}
    		}
    	}
        
        return map.get(node);
    }
	
	/**
	 * 
	 */
	public CloneGraph() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}

}
